home *** CD-ROM | disk | FTP | other *** search
/ Hacker's Secrets 4 / Hacker's Secrets 4.iso / misc / skey.txt < prev    next >
Text File  |  1996-04-26  |  11KB  |  276 lines
  1. Description of The S/KEY One-Time Password System
  2.   
  3.    Neil M. Haller    nmh@thumper.bellcore.com
  4.    Philip R. Karn    karn@chicago.qualcomm.com
  5.   
  6.   
  7.                 ABSTRACT
  8.  
  9. The S/KEY one-time password system provides authentication over networks
  10. that are subject to eavesdropping/reply attacks. This system has several
  11. advantages compared with other one-time or multi-use authentication
  12. systems.  The user's secret password never crosses the network during
  13. login, or when executing other commands requiring authentication such as
  14. the UNIX passwd or su commands.  No secret information is stored anywhere,
  15. including the host being protected, and the underlying algorithm may be
  16. (and it fact, is) public knowledge. The remote end of this system can run
  17. on any locally available computer.  The host end could be integrated into
  18. any application requiring authentication.
  19.  
  20.  
  21. Trademarks
  22. ----------
  23.    Athena and Kerberos of trademarks of MIT.
  24.    S/KEY is a trademark of Bellcore.
  25.    SPX and DEC are trademarks of Digital Equipment Company.
  26.    UNIX is a registered trademark of UNIX System Laboratories, Inc.
  27.  
  28.  
  29.  
  30. Attributes of the S/KEY One-Time Password System
  31. ------------------------------------------------
  32.  
  33. The S/KEY authentication system is a simple scheme that protects user
  34. passwords against passive attacks.  It is not as powerful or general in
  35. scope as Kerberos or SDASS; nor does it protect against active attacks.
  36. It can, however, be easily and quickly added to almost any UNIX system
  37. without requiring any additional hardware and without requiring the
  38. system to store information (such as plain text passwords) that would
  39. be more sensitive than the encrypted passwords already stored.  The
  40. S/KEY system can be used with non programmable terminals or personal
  41. computers (e.g., systems running DOS or Apple Macintoshes) with
  42. conventional communications programs.
  43.  
  44. Some of the properties of the S/KEY system are:
  45.  
  46.    o    Eavesdropping protection
  47.  
  48.    o    Conceptually simple and easy to use
  49.  
  50.    o    Based on a memorized secret password; does not require a
  51.     special device although it can easily be adapted to do so.
  52.  
  53.    o    Can be automated for authentication from a trusted system.
  54.     (Can also be partially automated for fast operation.)
  55.  
  56.    o    No secret algorithms.
  57.  
  58.    o    No secrets stored on host.
  59.  
  60.  
  61.  
  62. Description of the S/KEY One-Time Password System
  63. -------------------------------------------------
  64.  
  65. There are two sides to the operation of our one-time password system.
  66. On the user (or client) side, the appropriate one-time password must
  67. be generated.  On the system (server) side, the one-time password must
  68. be verified.  One time passwords are generated and verified using a
  69. one-way function based on MD4 [Rivest].  (Conversion to MD5 would be
  70. trivial)  
  71.  
  72. We have defined our one-way function to take 8 bytes of input and to
  73. produce 8 bytes of output.  This is done by running the 8 bytes of
  74. input through MD4 and then "folding" pairs of bytes in the 16-byte MD4
  75. output down to 8 bytes with exclusive-OR operations.  This allows us to
  76. apply the one-way function an arbitrary number of times.
  77.  
  78.  
  79. Generation of One-Time Passwords 
  80.  
  81. The sequence of one-time passwords is produced by applying the one-way
  82. function multiple times.  That is, the first one-way password is
  83. produced by running the user's secret password (s) through the one-way
  84. function some specified number of times, (n).  Assuming n=4,
  85.  
  86.             p(1) =  f(f(f(f(s))))
  87.  
  88. The next one-way password is generated by running the user's password
  89. through the one-way function only n-1  times.
  90.   
  91.             p(2) = f(f(f(s))) 
  92.  
  93. An eavesdropper who has monitored the use of the one-time password  
  94. p(i) will not be able to generate the next one in the sequence p(i+1)
  95. because doing so would require inverting the one-way function. Without
  96. knowing the secret key that was the starting point of the function
  97. iterations, this can not be done.
  98.  
  99. Seeding the Password
  100.  
  101. A user might want to use the same secret password on several machines,
  102. or might allow the iteration count to go to zero.  An initial step
  103. concatenates a seed with the arbitrary length secret password, crunches
  104. the result with MD4, and folds the result to 64 bits.  The result of
  105. this process is then iterated n times.
  106.  
  107.  
  108. System Verification of Passwords 
  109.  
  110. The host computer first saves a copy of the one-time password it
  111. receives, then it applies the one-way function to it.  If the result
  112. does not match the copy stored in the system's password file, then the
  113. request fails.  If they match, then the user's entry in the system
  114. password file is updated with the copy of the one-time password that
  115. was saved before the final execution (by the server) of the one-way
  116. function.  This updating advances the password sequence.
  117.  
  118. Because the number of one-way function iterations executed by the user
  119. decreases by one each time, at some point the user must reinitialize the
  120. system or be unable to log in again.  This is done by executing a
  121. special version of the passwd command to start a new sequence of
  122. one-time passwords.  This operation is essentially identical to a
  123. normal authentication, except that the one-time password receive
  124. over the network is not checked against the entry already in the
  125. password file before it replaces it. In this way, the selection of a
  126. new password can be done safely even in the presence of an eavesdropper.
  127.  
  128.  
  129. Operation of S/KEY One-Time Password System
  130. -------------------------------------------
  131.  
  132. Overview 
  133.  
  134. The S/KEY one-time password authentication system uses computation to
  135. generate a finite sequence of single-use passwords from a single secret.
  136. The security is entirely based on a single secret that is known only to
  137. the user. Alternatively, part of or the entire secret can be stored in a
  138. non-retrievable way, in the computing device.
  139.  
  140.  
  141. Generation of S/KEY One-Time Passwords 
  142.  
  143. As mentioned above, the one-time password sequence is derived from the
  144. secret password using a computer.  The required computation has been
  145. executed on a variety of PC and UNIX class machines including notebook
  146. and palm-tops. A vendor has estimated that credit card size devices
  147. could be built for less than $30 in large quantities.
  148.  
  149. The program can also be stored on and executed from a standard floppy
  150. disk.  This would allow operation on a remote computer that could not be
  151. entirely trusted not to contain a Trojan Horse that would attempt
  152. to capture the secret password.  It is sometimes useful to pre-compute
  153. and print several one-time passwords.  These could be carried on a trip
  154. where public terminals or workstations were available, but no trusted
  155. local computation was available. 
  156.  
  157.  
  158. Description of Operation 
  159.  
  160. The following narrative describes the procedure for logging into a UNIX
  161. system using the S/KEY one-time password system.  To illustrate the
  162. most complex case, we assume a hand-held PC compatible computer is used.
  163.  
  164.   o  The user, call her Sue, identifies herself to the system by login name.
  165.  
  166.   o  The system issues a challenge including the sequence number of the
  167.      one-time password expected and a "seed" that is unique to the system.
  168.      This "seed" allows Sue to securely use a single secret for several
  169.      machines.  Here the seed is "unix3" and the sequence number is 54.
  170.  
  171.   o  Sue enters 54 and unix3 into her palm-top computer.  She is prompted
  172.      for her secret password.
  173.  
  174.   o  Sue enters her secret password that may be of any length.  The palm-top
  175.      computes the 54th one-time password and displays it.
  176.  
  177.   o  Sue enters the one-time password and is authenticated.
  178.  
  179.   o  Next time Sue wants access, she will be prompted for one-time
  180.      password sequence number 53.
  181.  
  182.  
  183. Semi-Automated Operation 
  184.  
  185. The complexity illustrated above is necessary only when using a terminal
  186. that is not programmable by the user, or when using a non-trusted
  187. terminal.  We have built semi-automatic interfaces for clients using
  188. communications software on popular personal computers.  The following
  189. example illustrates logging in using a trusted personal computer and a
  190. popular terminal emulation program.
  191.  
  192.   o  Before starting the communication program, Sue runs the CTKEY
  193.      program that ties a TSR to a "hot-key" such as F10.
  194.  
  195.   o  Sue identifies herself by login name as above.
  196.  
  197.   o  The system issues the same challenge including the seed "unix3"
  198.      and the sequence number 54.  The host system now expects an
  199.      s/key one-time password.
  200.  
  201.   o  Sue presses the hot-key and is then prompted for a secret password
  202.      by the TSR program on the local system.
  203.  
  204.   o  In response to Sue's secret password, the 54th one-time password
  205.      is displayed at the position of the cursor.
  206.  
  207.   o  Sue presses "Insert" and the terminal emulator transmits the
  208.      one-time password completing the authentication.
  209.  
  210. If the personal computer were in a trusted location, an option of the
  211. CTKEY program allows the secret password to be stored in a local file.
  212.  
  213.  
  214. Form of Password 
  215.  
  216. Internally the one-time password is a 64 bit number.  Entering a 64 bit
  217. number is not a pleasant task.  The one-time password is therefore
  218. converted to a sequence of six short words (1 to 4 letters). Each word
  219. is chosen from a dictionary of 2048 words.  The contents of this
  220. dictionary is not a secret.
  221.  
  222.  
  223. Source Screening 
  224.  
  225. It is frequently desirable to allow internal access with a multi-use
  226. password while requiring one-time passwords for external access.
  227. A screening table provides this function.  When this table is present,
  228. login attempts that pass the screening test are permitted to use the
  229. normal password or a one-time password.  Others are notified that the
  230. use of the one-time password is required.
  231.  
  232.  
  233. Password echo 
  234.  
  235. Normally systems disable printing during the typing of a password so
  236. that an onlooker cannot steal the password.  With a one-time password,
  237. this is unnecessary.  The replacement  login  command allows the user
  238. to turn echo on by pressing "return" at the password prompt.  This
  239. makes it easier to enter the longer one-time password.
  240.  
  241.  
  242. Acknowledgments
  243. ---------------
  244. The idea behind our system was originally described by Leslie Lamport. 
  245. Some details of the design were contributed by John S. Walden who
  246. wrote the initial version of the client software.
  247.  
  248.  
  249. References
  250. ----------
  251.  
  252. Eugene H. Spafford, "The internet worm program: An analysis."  Computer
  253. Communications Review 19(1):17-57, January 1989.
  254.  
  255.  
  256. D. C. Feldmeier and P. R. Karn, "UNIX Password Security - Ten Years
  257. Later", Crypto '89 Conference , Santa Barbara, CA August 20-24, 1989.
  258.  
  259.  
  260. J. G. Steiner, C. Neuman, and J. I. Schiller. "Kerberos: An
  261. authentication service for open network systems."   USENIX Conference
  262. Proceedings, pp. 191-202, Dallas, Texas, February 1988.
  263.  
  264.  
  265. Catherine R. Avril and Ronald L. Orcutt. Athena: MIT's Once and
  266. Future Distributed Computing Project.  Information
  267. Technology Quarterly , Fall 1990, pp. 4-11.
  268.  
  269.  
  270. R. L. Rivest, The MD4 Message Digest Algorithm,  Crypto '90 Abstracts
  271. (August 1990), 281-291.
  272.  
  273.  
  274. Leslie Lamport, "Password Authentication with Insecure Communication",
  275.  Communications of the ACM  24.11 (November 1981), 770-772.
  276.